var DIR = [[0,1], [1,0], [0,-1], [-1,0], [1,-1], [1,1], [-1,1], [-1,-1]];
var COST = [1, 1, 1, 1, 1.42, 1.42, 1.42, 1.42];
var NUM = 20, LEN = 15;
var ENQUEUE = 0, DEQUEUE = 1, CHANGEPRE = 2;
function distance_to_target(x, y, dir, tx, ty) {
	x += DIR[dir][0];
	y += DIR[dir][1];
	var dx = x-tx, dy = y-ty;
	return Math.sqrt(dx*dx + dy*dy);
}
function queue() {   // priority queue, minimum heap is a better implement
	var array = [];
	var cmp = function(a, b)   { return b.heuristic - a.heuristic; }
	this.push = function(n) {
		array.push(n);
		array.sort(cmp);   // not a good idea , hmmm ... well , but it is work
	}
	this.top = function() {
		if (array.length === 0)   return;
		return array[array.length - 1];
	}
	this.pop = function() {
		if (array.length === 0)   return;
		return array.pop();
	}
	this.empty = function() { return array.length === 0 ? true : false; }
}
function cell() {
	this.marked = false;	// am I already searched
	this.inqueue = false;	// am I in queue
    this.distance = 0;		// distance from start
    this.lastx = -1;		// father node's x
	this.lasty = -1;		// father node's y
    this.passable = true;	// am I passable
}
function coord(x, y, h) {
	this.x = x;
	this.y = y;
	this.heuristic = h;
}
function step() {
	this.com=0, this.x=0, this.y=0, this.newx=0, this.newy=0;
	if (arguments.length==3) {
		this.com=arguments[0];
		this.x=arguments[1];
		this.y=arguments[2];
	} else if (arguments.length==5) {
		this.com=arguments[0];
		this.x=arguments[1];
		this.y=arguments[2];
		this.newx=arguments[3];
		this.newy=arguments[4];
	}
}

var BFS = new Object();
var GOAL = new Object();
var ASTAR = new Object();

BFS.map = [];
BFS.steps = [];
for (var i=0;i<NUM;i++)   BFS.map[i] = [];
for (var y=0;y<NUM;y++) { for (var x=0;x<NUM;x++)   BFS.map[y][x] = new cell(); }

GOAL.map = [];
GOAL.steps = [];
for (var i=0;i<NUM;i++)   GOAL.map[i] = [];
for (var y=0;y<NUM;y++) { for (var x=0;x<NUM;x++)   GOAL.map[y][x] = new cell(); }

ASTAR.map = [];
ASTAR.steps = [];
for (var i=0;i<NUM;i++)   ASTAR.map[i] = [];
for (var y=0;y<NUM;y++) { for (var x=0;x<NUM;x++)   ASTAR.map[y][x] = new cell(); }

function reset_steps() {
	BFS.steps = [];
	GOAL.steps = [];
	ASTAR.steps = [];
}

function reset_map_state() {
	for (var y=0; y<NUM; y++) {
		for (var x=0; x<NUM; x++) {
			BFS.map[y][x].marked = false;
			BFS.map[y][x].inqueue = false;
			BFS.map[y][x].distance = 0;
			BFS.map[y][x].lastx = BFS.map[y][x].lasty = -1;
			
			GOAL.map[y][x].marked = false;
			GOAL.map[y][x].inqueue = false;
			GOAL.map[y][x].distance = 0;
			GOAL.map[y][x].lastx = GOAL.map[y][x].lasty = -1;
			
			ASTAR.map[y][x].marked = false;
			ASTAR.map[y][x].inqueue = false;
			ASTAR.map[y][x].distance = 0;
			ASTAR.map[y][x].lastx = ASTAR.map[y][x].lasty = -1;
		}
	}
}

function search_BFS(sx, sy, ex, ey) {
	var q = new queue();
	reset_map_state();
	
	q.push(new coord(sx, sy, 0));
	BFS.steps.push(new step(ENQUEUE, sx, sy));
	
	while (!q.empty()) {
		var x = q.top().x;
		var y = q.top().y;
		q.pop();
		BFS.steps.push(new step(DEQUEUE, x, y));
		
		if (!BFS.map[y][x].marked) {
			BFS.map[y][x].marked = true;
			if (x == ex && y == ey)   break;   // reach target
			for (var dir=0; dir<8; dir++) {
				var ax = x + DIR[dir][0];
				var ay = y + DIR[dir][1];
				if (ax>=0 && ax<NUM && ay>=0 && ay<NUM && BFS.map[ay][ax].passable && !BFS.map[ay][ax].marked) {
					var dis = BFS.map[y][x].distance + COST[dir];
					if (BFS.map[ay][ax].lastx != -1) {
						if (dis < BFS.map[ay][ax].distance) {   // re-link path node
							BFS.map[ay][ax].lastx = x;
							BFS.map[ay][ax].lasty = y;
							BFS.map[ay][ax].distance = dis;
							q.push(new coord(ax, ay, dis));
							BFS.steps.push(new step(CHANGEPRE, ax, ay, x, y));
						}
					} else {                                    // init linked path node
						BFS.map[ay][ax].lastx = x;
						BFS.map[ay][ax].lasty = y;
						BFS.map[ay][ax].distance = dis;
						q.push(new coord(ax, ay, dis));
						BFS.steps.push(new step(ENQUEUE, ax, ay));
						BFS.steps.push(new step(CHANGEPRE, ax, ay, x, y));
					}
				}
			}
		}
	}
}
function search_GOAL(sx, sy, ex, ey) {
	var q = new queue();
	reset_map_state();
	
	q.push(new coord(sx, sy, 0));
	GOAL.steps.push(new step(ENQUEUE, sx, sy));
	
	while (!q.empty()) {
		var x = q.top().x;
		var y = q.top().y;
		q.pop();
		GOAL.steps.push(new step(DEQUEUE, x, y));
		
		if (!GOAL.map[y][x].marked) {
			GOAL.map[y][x].marked = true;
			if (x == ex && y == ey)   break;   // reach target
			for (var dir=0; dir<8; dir++) {
				var ax = x + DIR[dir][0];
				var ay = y + DIR[dir][1];
				if (ax>=0 && ax<NUM && ay>=0 && ay<NUM && GOAL.map[ay][ax].passable && !GOAL.map[ay][ax].marked) {
					var dis = GOAL.map[y][x].distance + COST[dir];
					if (GOAL.map[ay][ax].lastx != -1) {
						if (dis < GOAL.map[ay][ax].distance) {   // re-link path node
							GOAL.map[ay][ax].lastx = x;
							GOAL.map[ay][ax].lasty = y;
							GOAL.map[ay][ax].distance = dis;
							var c = new coord(ax, ay, 0);
							c.heuristic = distance_to_target(x, y, dir, ex, ey);
							q.push(c);
							GOAL.steps.push(new step(CHANGEPRE, ax, ay, x, y));
						}
					} else {                                     // init linked path node
						GOAL.map[ay][ax].lastx = x;
						GOAL.map[ay][ax].lasty = y;
						GOAL.map[ay][ax].distance = dis;
						var c = new coord(ax, ay, 0);
						c.heuristic = distance_to_target(x, y, dir, ex, ey);
						q.push(c);
						GOAL.steps.push(new step(ENQUEUE, ax, ay));
						GOAL.steps.push(new step(CHANGEPRE, ax, ay, x, y));
					}
				}
			}
		}
	}
}
function search_ASTAR(sx, sy, ex, ey) {
	var q = new queue();
	reset_map_state();
	
	q.push(new coord(sx, sy, 0));
	ASTAR.steps.push(new step(ENQUEUE, sx, sy));
	
	while (!q.empty()) {
		var x = q.top().x;
		var y = q.top().y;
		q.pop();
		ASTAR.steps.push(new step(DEQUEUE, x, y));
		
		if (!ASTAR.map[y][x].marked) {
			ASTAR.map[y][x].marked = true;
			if (x == ex && y == ey)   break;   // reach target
			for (var dir=0; dir<8; dir++) {
				var ax = x + DIR[dir][0];
				var ay = y + DIR[dir][1];
				if (ax>=0 && ax<NUM && ay>=0 && ay<NUM && ASTAR.map[ay][ax].passable && !ASTAR.map[ay][ax].marked) {
					var dis = ASTAR.map[y][x].distance + COST[dir];
					if (ASTAR.map[ay][ax].lastx != -1) {
						if (dis < ASTAR.map[ay][ax].distance) {   // re-link path node
							ASTAR.map[ay][ax].lastx = x;
							ASTAR.map[ay][ax].lasty = y;
							ASTAR.map[ay][ax].distance = dis;
							c = new coord(ax, ay, 0);
							c.heuristic = distance_to_target(x, y, dir, ex, ey) + dis;
							q.push(c);
							ASTAR.steps.push(new step(CHANGEPRE, ax, ay, x, y));
						}
					} else {                                      // init linked path node
						ASTAR.map[ay][ax].lastx = x;
						ASTAR.map[ay][ax].lasty = y;
						ASTAR.map[ay][ax].distance = dis;
						c = new coord(ax, ay, 0);
						c.heuristic = distance_to_target(x, y, dir, ex, ey) + dis;
						q.push(c);
						ASTAR.steps.push(new step(ENQUEUE, ax, ay));
						ASTAR.steps.push(new step(CHANGEPRE, ax, ay, x, y));
					}
				}
			}
		}
	}
}